낱말 분석
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
낱말 분석은 프로그래밍 언어의 소스 코드를 분석하는 과정으로, 입력 문자열을 토큰으로 분할하고 분류하는 어휘 분석과정을 거친다. 어휘 분석은 스캐너와 평가기 두 단계로 나뉘며, 스캐너는 렉심을 토큰 클래스로 분류하고, 평가기는 렉심을 처리된 값으로 변환한다. 어휘 분석은 어휘 문법에 따라 진행되며, 공백 문자, 주석 처리, 줄 연속, 세미콜론 삽입, 오프사이드 규칙 등과 같은 구문 구조를 처리한다. 렉서 생성기를 사용하여 렉서를 생성할 수 있으며, 문맥 의존적 렉싱과 같은 복잡한 경우도 존재한다.
더 읽어볼만한 페이지
- 구문 분석 - 패턴 매칭
패턴 매칭은 데이터 구조나 문자열에서 특정 패턴을 찾아 식별하는 기법으로, 다양한 프로그래밍 언어와 시스템에서 사용되며 데이터 필터링, 추출 및 선언적 프로그래밍에 중요한 역할을 수행한다. - 구문 분석 - 구문 오류
구문 오류는 계산기의 입력된 수식의 구문이 잘못되었음을 의미하며, 괄호 누락, 음수 기호와 빼기 기호의 잘못된 사용 등 다양한 형태로 발생한다. - 프로그래밍 언어 구현 - 어셈블리어
어셈블리어는 사람이 이해하기 쉬운 니모닉 기호로 기계어 명령을 표현하는 저수준 프로그래밍 언어로서, 각 프로세서마다 사양이 다른 어셈블리어가 존재하며 하드웨어 직접 제어, 성능 최적화, 저수준 시스템 프로그래밍 등에 활용된다. - 프로그래밍 언어 구현 - 컴파일러
컴파일러는 고급 프로그래밍 언어로 작성된 소스 코드를 컴퓨터가 이해할 수 있는 저급 언어로 변환하는 프로그램으로, 어휘 분석, 구문 분석, 의미 분석, 최적화, 코드 생성 등의 단계를 거쳐 목적 코드를 생성하며, 네이티브 컴파일러, 크로스 컴파일러 등으로 분류되어 다양한 분야에서 활용된다. - 컴파일러 구성 - 구문 분석
구문 분석은 입력 데이터를 구조화된 형태로 변환하는 과정으로, 컴퓨터 언어에서는 소스 코드를 분석하여 추상 구문 트리를 생성하고, 자연어 처리에서는 텍스트의 문장 구조와 의미를 분석한다. - 컴파일러 구성 - 바이너리 재컴파일러
| 낱말 분석 | |
|---|---|
| 개요 | |
| 유형 | 어휘 분석 |
| 분야 | 컴파일러, 프로그래밍 언어 |
| 관련 개념 | 토큰 구문 분석 정규 표현식 |
| 상세 정보 | |
| 역할 | 소스 코드를 토큰 시퀀스로 변환 |
| 입력 | 소스 코드 (문자열) |
| 출력 | 토큰 시퀀스 |
| 사용 도구 | lex flex ANTLR |
| 예시 | 정규 표현식 기반 토큰 정의 상태 기계 기반 토큰 인식 |
2. 토큰
토큰은 파싱을 위해 분류된 어휘 항목을 나타내는 구조이다.[1] 토큰은 일반적으로 어휘소와 토큰 분류의 쌍으로 표현된다.
다음은 토큰화의 예시이다.
| 어휘소 | 토큰 분류 |
|---|---|
| sum | Identifier |
| = | Assignment operator |
| 3 | Integer literal |
| + | Addition operator |
| 2 | Integer literal |
| ; | End of statement |
어휘 토큰화를 수행하는 규칙 기반 프로그램은 토크나이저[1] 또는 스캐너라고 불린다. 렉서와 파서는 컴파일러에 가장 많이 사용되지만, 프리티 프린터나 린터와 같은 다른 컴퓨터 언어 도구에도 사용될 수 있다.
규칙 기반 자연어 처리에서 "어휘소"라고 불리는 것은 언어학에서 "어휘소"라고 불리는 것과 같지 않다. 규칙 기반 자연어 처리에서 "어휘소"라고 불리는 것은 분석 언어에서만 언어학적 의미와 같을 수 있지만, 융합어와 같은 고도로 합성 언어에서는 그렇지 않다.
어휘 분석은 자연어 처리와 프로그래밍 언어의 컴파일에서 수행된다.[11]
문자열에서 토큰을 구축하려면 어휘 분석기에는 평가기가 필요하다. 평가기는 문자열에 "값"을 부여한다. 괄호와 같은 일부 토큰은 "값"을 갖지 않으므로 평가기는 아무것도 반환하지 않는다. 최종적으로 토큰 열을 얻을 수 있다.
2. 1. 토큰의 예시 (C 언어)
C 언어 코드::
sum = 35 + 21;는 다음과 같이 토큰화된다.[12]
| 문자열 | 타입 |
|---|---|
sum | 식별자 |
= | 할당 연산자 |
35 | 수 |
+ | 덧셈 연산자 |
21 | 수 |
; | 세미콜론 |
어휘 분석은 자연어 처리 및 프로그래밍 언어의 컴파일 과정에서 수행된다.[11] 이 과정은 일반적으로 스캐닝과 평가 두 단계로 나뉜다.
토큰은 어휘 분석 단계에서 프로그램 요소로서의 타당성이 고려되지 않을 수 있다. 예를 들어, 위의 예에서 `sum`이 이전에 선언되지 않았다면 의미가 없지만, 어휘 분석기는 일반적으로 토큰으로 취급한다.[12]
3. 어휘 분석의 과정
렉서는 입력 문자열(문자열)을 언어적으로 의미있는 최소 단위인 토큰(token(s)영어)으로 분해하는 처리를 담당하며, 이러한 작업을 자동으로 수행하는 프로그램을 어휘 분석기(lexical analyser영어)라고 한다.
토큰은 파싱을 위해 분류를 명시적으로 지시하는 어휘소를 표현하는 구조이다.[19] 예를 들어 다음과 같은 표로 토큰화되어 표현될 수 있다.
| 어휘소 | 토큰 분류 |
|---|---|
| sum | Identifier |
| = | Assignment operator |
| 3 | Integer literal |
| + | Addition operator |
| 2 | Integer literal |
| ; | End of statement |
어휘 분석기는 부분 문자열에서 토큰을 구축하기 위해 두 번째 단계인 평가기가 필요하다. 평가기는 문자열에 "값"을 부여한다.[3] 문자열과 형식을 결합한 것이 토큰을 나타내며, 구문 분석기에 입력될 수 있다.[3]
3. 1. 스캐너
스캐너는 입력 문자열을 렉심(lexeme)이라는 구문 단위로 분할하고, 이를 토큰 클래스로 분류하는 작업을 수행한다.[1] 이 과정은 렉싱의 첫 단계이며, 컴파일러 프런트엔드의 첫 단계를 구성한다. 스캐너는 일반적으로 유한 상태 기계(FSM)를 기반으로 하며, 처리하는 토큰 내에 포함될 수 있는 가능한 문자 시퀀스에 대한 정보를 인코딩한다.[11]예를 들어, '정수' 렉심은 일련의 숫자 문자를 포함할 수 있다. 대부분의 경우, 첫 번째 공백이 아닌 문자를 사용하여 뒤따르는 토큰의 종류를 추론하고, 해당 토큰에 허용되는 문자 집합에 없는 문자에 도달할 때까지 후속 입력 문자를 처리한다. 이를 '최대 멈춤' 또는 '최장 일치' 규칙이라고 한다.[11]
C 언어와 같이 일부 언어에서는 렉셈 생성 규칙이 더 복잡할 수 있으며, 이전에 읽은 문자에 대한 백트래킹이 필요할 수 있다.[11]
3. 2. 평가기
렉서는 렉심을 처리된 값으로 변환하는 평가기를 가진다.[19] 괄호와 같이 값을 갖지 않는 토큰도 있다.[19]평가기는 어휘소의 문자를 검토하여 '값'을 생성한다.[1] 어휘소의 유형과 값을 결합한 것이 파서에 제공될 수 있는 토큰을 구성한다.[1] 괄호와 같은 일부 토큰은 값을 갖지 않아 평가기 함수가 아무것도 반환하지 않을 수 있다.[1] 유형만 필요한 경우도 있다.[1] 평가기는 어휘소를 억제하여 파서로부터 숨길 수 있는데, 이는 공백과 주석에 유용하다.[1]
식별자의 평가기는 일반적으로 단순하지만, 언스트로핑을 포함할 수 있다.[1] 정수 리터럴의 평가기는 문자열을 전달하거나, 자체 평가를 수행할 수 있다.[1] 간단한 인용된 문자열 리터럴의 평가기는 따옴표만 제거하면 되지만, 이스케이프된 문자열 리터럴의 평가기는 이스케이프 시퀀스를 언이스케이프하는 렉서를 통합한다.[1]
부분 문자열에서 토큰을 구축하기 위해 어휘 분석기는 두 번째 단계인 평가기가 필요하다. 평가기는 문자열에 "값"을 부여한다.[3] 문자열과 형식을 결합한 것이 토큰을 나타내며, 구문 분석기에 입력될 수 있다.[3] 괄호와 같은 일부 토큰은 "값"을 가지지 않으므로, 평가기 함수는 아무것도 반환하지 않는다.[3] 정수, 식별자, 문자열 등을 처리하는 평가기는 매우 복잡해진다. 공백이나 주석 등은 그대로 버리는 경우도 있다.[3]
4. 어휘 문법
프로그래밍 언어의 명세는 종종 어휘 구문을 정의하는 규칙 집합인 어휘 문법을 포함한다. 어휘 구문은 일반적으로 정규 언어로 표현되며, 문법 규칙은 정규 표현식으로 구성된다. 이는 토큰의 가능한 문자 시퀀스(렉심) 집합을 정의한다. 렉서는 문자열을 인식하고, 발견된 각 종류의 문자열에 대해 어휘 프로그램은 작업을 수행하며, 가장 간단하게는 토큰을 생성한다.[1]
렉서는 일반적으로 매우 단순하며, 대부분의 복잡성은 구문 분석 또는 의미 분석 단계로 미뤄진다. 렉서는 종종 렉서 생성기, 특히 렉스 또는 그 파생물에 의해 생성될 수 있다. 그러나 렉서는 때때로 입력을 더 쉽게 만들고 파서를 단순화하기 위해 구조화 처리를 하는 등의 일부 복잡성을 포함할 수 있으며, 더 많은 기능을 지원하거나 성능을 위해 부분적으로 또는 완전히 수동으로 작성될 수도 있다.[1]
어휘 분석은 컴퓨터를 사용한 자연어 처리와 프로그래밍 언어의 컴파일 모두에서 수행된다.[11] 자연어 문장이든, 프로그램의 소스 코드이든, 문장은 결국 문자, 기호, 구두점 등이 다수 나열된 것([문자열])이지만, 어휘 분석은 이것을 언어적으로 의미 있는 최소 단위인 토큰(token영어)으로 분해하는 처리이다. 문장을 분석하여 토큰으로 분해하는 작업을 자동으로 수행하는 프로그램을 어휘 분석기(lexical analyser영어)라고 한다.
4. 1. 공백 문자와 주석
공백 문자와 주석은 프로그래밍 언어 문법에 정의되어 렉서에 의해 처리되지만, 일반적으로 토큰을 생성하지 않고 폐기된다.[19] 이들은 '의미 없음'으로 간주되어 `if x`처럼 토큰을 분리하는 역할만 수행한다. ( `ifx`와는 다르게 인식)그러나 두 가지 중요한 예외가 있다.
- 오프사이드 규칙 언어에서는 초기 공백이 블록 구조를 결정하므로 렉서 수준에서 중요하게 처리된다.
- 예쁘게 인쇄 프로그램이나 디버깅 도구와 같이 주석과 공백을 보존해야 하는 경우도 있다.
1960년대 ALGOL에서는 공백과 주석이 컴파일러 프론트 엔드의 초기 단계인 줄 재구성 단계에서 제거되었으나, 현재는 렉서에서 처리된다.[19]
5. 어휘 분석의 어려움
단어 경계를 사용하는 언어(대부분 라틴 문자를 사용하는 언어와 프로그래밍 언어)에서는 토큰화가 비교적 간단하지만, 축약형, 하이픈이 있는 단어, 이모티콘, URI 등은 고려해야 할 예외 사항이다.[19] 예를 들어 "New York-based"와 같은 단어는 단순한 토크나이저가 공백을 기준으로 분할할 수 있지만, 하이픈을 기준으로 분할하는 것이 더 나을 수 있다.
고대 그리스어, 중국어[4], 태국어와 같이 단어 경계가 없는 언어에서는 토큰화가 특히 어렵다. 한국어와 같은 교착어 역시 토큰화 작업을 복잡하게 만든다.
이러한 문제를 해결하기 위해 복잡한 휴리스틱을 개발하거나, 일반적인 특수 사례 표를 조회하거나, 언어 모델에 토큰을 맞추는 등의 방법이 사용될 수 있다.
6. 렉서 생성기
렉서 생성기는 렉싱 사양을 받아 렉서를 자동으로 생성하는 도구이다. 대표적인 렉서 생성기로는 Lex, Flex, re2c 등이 있다.[5][14]
Lex는 1975년 마이크 레스크(:en:Mike Lesk)와 에릭 슈미트가 개발한 어휘 분석기 생성기로, POSIX에도 채택되었다. Lex는 토큰 규칙을 정규 표현식으로 기술한 문서를 기반으로 어휘 분석기를 자동으로 만든다. 입력이 규칙과 일치하지 않으면 오류로 처리한다.[1]
Flex는 1987년경 Lex를 :en:Vern Paxson이 개량하여 출시한 것으로, 널리 사용되고 있다. 대부분의 Linux 배포판에서 Flex를 표준으로 채택하고 있다. Lex 계열 생성기는 표 구동형 방식을 사용한다.[1]
re2c는 1994년 Peter Bumbulis가 개발한 렉서 생성기이다.[14] re2c는 Flex보다 2~3배 빠른 어휘 분석기를 생성한다고 알려져 있다.[5]
2017년에는 Frank-Rene Schaefer가 개발한 quex가 출시되었다.[15] quex 역시 고속 어휘 분석기를 생성한다.
7. 구문 구조
어휘 분석은 단순한 토큰화를 넘어 문장 구조를 파악하는 단계까지 확장될 수 있다. 1960년대에는 ALGOL과 같은 언어에서 공백 문자와 주석을 제거하는 별도의 단계가 있었지만, 현재는 렉서에서 처리된다.
오프사이드 규칙 언어에서 초기 공백은 블록 구조를 결정하므로 중요하며, 렉서 수준에서 처리된다. 예를 들어 파이썬에서는 들여쓰기가 늘어나면 렉서가 INDENT 토큰을, 줄어들면 DEDENT 토큰을 내보낸다. 이러한 토큰은 중괄호(`{` 및 `}`)를 사용하는 언어의 여는/닫는 중괄호와 유사하다. 렉서는 들여쓰기 레벨의 스택을 유지하여 들여쓰기 변경을 감지하므로, 어휘 문법은 문맥 자유적이 아니다.[10]
7. 1. 줄 연속
일부 언어에서는 줄 바꿈이 일반적으로 구문 종결자 기능을 한다. 대부분의 경우, 줄을 백슬래시로 끝내면(바로 뒤에 줄 바꿈이 옴) 줄이 ''이어집니다''. 즉, 다음 줄이 이전 줄에 ''결합''된다. 이는 일반적으로 렉서에서 수행된다. 백슬래시와 줄 바꿈은 토큰화되는 대신 폐기된다. 예시로는 배시,[6] 다른 셸 스크립트 및 파이썬이 있다.[7]7. 2. 세미콜론 삽입
많은 프로그래밍 언어들은 세미콜론(;)을 문장 종결자로 사용한다. 대부분의 경우 세미콜론은 필수적이지만, 일부 언어에서는 선택 사항이다. 렉서는 입력 문자 스트림에 세미콜론이 없더라도 토큰 스트림에 세미콜론을 출력하는데, 이를 세미콜론 삽입 또는 자동 세미콜론 삽입이라고 한다.[1] 이러한 경우 세미콜론은 언어의 형식적인 구문 문법의 일부이지만, 렉서가 삽입하므로 입력 텍스트에서 생략될 수 있다. 선택적 세미콜론은 후행 쉼표 또는 세미콜론의 경우처럼 파서 단계에서 처리되기도 한다.세미콜론 삽입은 BCPL과 Go의 기능이지만,[8] B나 C에는 존재하지 않는다.[9] 자바스크립트에도 존재하지만, 규칙이 다소 복잡하고 비판을 많이 받는다. 버그를 방지하기 위해 항상 세미콜론을 사용하거나, 모호한 문장의 시작 부분에 방어적 세미콜론을 사용하기도 한다.
세미콜론 삽입과 줄 연속은 상호 보완적인 것으로 볼 수 있다. 세미콜론 삽입은 줄 바꿈이 토큰을 생성하지 *않음*에도 토큰을 추가하는 반면, 줄 연속은 줄 바꿈이 토큰을 생성 *함*에도 토큰 생성을 방지한다.
7. 3. 오프사이드 규칙
오프사이드 규칙(들여쓰기로 블록을 결정하는 방법)은 렉서에서 구현할 수 있다. 예를 들어 파이썬에서는 들여쓰기가 늘어나면 렉서가 INDENT 토큰을 내보내고, 들여쓰기가 줄어들면 렉서가 하나 이상의 DEDENT 토큰을 내보낸다.[10] 이러한 토큰들은 중괄호를 사용하여 블록을 표현하는 언어에서 여는 중괄호(`{`) 및 닫는 중괄호(`}`)에 해당한다. 이는 구문 문법이 중괄호나 들여쓰기 중 어느 것이 사용되는지에 의존하지 않는다는 것을 의미한다. 따라서 렉서는 상태(들여쓰기 레벨의 스택)를 유지해야 하므로 들여쓰기 변경을 감지할 수 있다. 이 때문에 어휘 문법은 문맥 자유적이 아니며, INDENT–DEDENT는 이전 들여쓰기 레벨이라는 문맥 정보에 따라 달라진다.8. 문맥 의존적 렉싱
일반적으로 어휘 문법은 문맥 자유적이어서 간단하고 효율적인 구현이 가능하다. 렉서에서 파서로의 단방향 통신을 통해 정보를 전달하며, 렉서로 다시 정보를 전달할 필요가 없다.[19]
하지만 예외도 존재한다. 예를 들어 Go에서는 세미콜론 삽입을 위해 하나의 토큰을 뒤돌아봐야 하고, Python에서는 연속된 문자열 리터럴 연결[7]을 위해 하나의 토큰을 버퍼에 보관해야 한다. 또한 Python의 오프사이드 규칙은 들여쓰기 레벨을 유지해야 한다. 이러한 예시는 렉서를 복잡하게 만들지만, 파서나 이후 단계에서는 드러나지 않는다.
더 복잡한 예시는 C 언어의 렉서 해킹이다. typedef 이름과 변수 이름은 어휘적으로 동일하지만, 의미 분석 단계까지는 토큰 클래스가 결정되지 않는다. 따라서 렉서는 의미 분석기를 호출하여 typedef 이름인지 확인해야 한다. 이 경우 정보는 의미 분석기에서 렉서로 다시 전달되어 설계가 복잡해진다.
참조
[1]
웹사이트
Anatomy of a Compiler and The Tokenizer
http://www.cs.man.ac[...]
[2]
서적
Compilers Principles, Techniques, & Tools, 2nd Ed.
https://stackoverflo[...]
[3]
웹사이트
Structure and Interpretation of Computer Programs
https://web.archive.[...]
2009-03-07
[4]
간행물
Rethinking Chinese Word Segmentation: Tokenization, Character Classification, or Word break Identification
http://www.aclweb.or[...]
2007
[5]
저널
RE2C: A more versatile scanner generator
1993-03-12
[6]
문서
Bash Reference Manual
https://www.gnu.org/[...]
[7]
웹사이트
3.6.4 Documentation
https://docs.python.[...]
[8]
문서
Effective Go
http://golang.org/do[...]
[9]
문서
Semicolons in Go
https://groups.googl[...]
2009-12-10
[10]
웹인용
Lexical analysis > Indentation
https://docs.python.[...]
2023-06-21
[11]
문서
IT用語辞典 e-words【字句解析】
[12]
서적
コンパイラの技術書のバイブル、Alfred V.Aho, Compilers,Principles, Techniques, and Tools
[13]
서적
Alfred V.Aho, Compilers,Principles, Techniques, and Tools
[14]
웹사이트
r2c公式サイト
http://re2c.org/
[15]
웹사이트
quexのsourceforge.net上の外部リンク
https://quex.sourcef[...]
[16]
웹인용
Anatomy of a Compiler and The Tokenizer
http://www.cs.man.ac[...]
[17]
뉴스
아이티플러스, 체인지마이너 ‘종합문자열분석기’ 특허취득
http://www.ddaily.co[...]
디지털데일리
2007-03-02
[18]
저널
USA(Universal String Analyzer)
http://academic.nave[...]
한국과학기술정보연구원
[19]
서적
Compilers Principles, Techniques, & Tools, 2nd Ed.
https://stackoverflo[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com